//
//  33.丑数.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/24.
//

import Foundation
/*
 题目：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 思路：1.暴力法：从1开始遍历++，巨耗时不推荐。
 思路：2.# 前面生成的每一个丑数都应该乘以2，3，5以产生新的丑数，但是我们不必比较前面的每一个丑数
        # 例如：假设前面的某个丑数a 因为乘以2 得到了当前的丑数b，下一次再生成下一个丑数时，就不用再考察a以及a前面的丑数*2的情况了，
        # 但是还要a乘以3或5的情况，以及前面的除了a以外的其他丑数（可能在a前面或后面）乘以2，3，5的情况
        idx2, idx3, idx5 = 0, 0, 0 # idx2表示上一个 是因为乘以2而产生的丑数的下标，其他依次类推
 */
func offer_33() {
    print(Solution().getUglyNumber_Solution2(10000))
}

fileprivate class Solution {
    func getUglyNumber_Solution1(_ index: Int) -> Int {
        guard index > 1 else { return 1 }
        var count = index - 1
        var i = 2
        while count > 0 {
            var j = i
            while true {
                if j % 2 == 0 {
                    j /= 2
                } else if j % 3 == 0 {
                    j /= 3
                } else if j % 5 == 0 {
                    j /= 5
                } else {
                    i += 1
                    j = i
                }
                if j == 1 {
                    i += 1
                    j = i
                    break
                }
            }
            count -= 1
        }
        return i - 1
    }
    
    func getUglyNumber_Solution2(_ index: Int) -> Int {
        guard index > 1 else { return index }
        var res = [Int](repeating: 0, count: index)
        res[0] = 1
        var t2 = 0, t3 = 0, t5 = 0
        for i in 1..<index {
            res[i] = min(res[t2]*2, res[t3]*3, res[t5]*5)
            if res[i] % 2 == 0 {
                t2 += 1
            }
            if res[i] % 3 == 0 {
                t3 += 1
            }
            if res[i] % 5 == 0 {
                t5 += 1
            }
        }
        return res.last!
    }
}


